package LeetCode.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.TraverseUtils;

/*
 * 
原题　
			 Given two arrays, write a function to compute their intersection.
	
	Example:
	Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].
	
	Note:
	
	    Each element in the result should appear as many times as it shows in both arrays.
	    The result can be in any order.

	
题目大意
	
	找出两个数组相同的元素，且返回的数组内元素不可重复
解题思路
	
 * @Date 2017-09-25 01：01
 */
public class _350_Intersection_of_Two_Arrays_II {

	public int[] intersect(int[] nums1, int[] nums2) {
		LinkedList<Integer> stack = new LinkedList<Integer>();
		Arrays.sort(nums1);
		Arrays.sort(nums2);
		//定义两个指针遍历两个数组
		int i = 0, j = 0;
		while (i<nums1.length && j<nums2.length) {
			if (nums1[i] < nums2[j]) {
				i ++;
			} else if (nums1[i] > nums2[j]) {
				j ++;
			} else {

                stack.add(nums1[i]);
				i ++;
				j ++;
			}
 		}
		return change2Result(stack);
	}

	private int[] change2Result(LinkedList<Integer> stack) {
		int[] rs = new int[stack.size()];
		for (int i = 0; i < stack.size(); i ++) {
			rs[i] = stack.get(i);
		}
//		TraverseUtils.println("349", rs);
		return rs;
	}
    
	public static void main(String[] args) {
		_350_Intersection_of_Two_Arrays_II obj = new _350_Intersection_of_Two_Arrays_II();
		obj.intersect(
				new int[] {
					1, 2, 2, 1
				}, 
				new int[] {
					2, 2,	
				});
	}
}
